package com.example.hot100;


public class Leetcode152_MaxProduct {
    public static void main(String[] args) {

        int[] nums = {2, 3, -2, 4};
        System.out.println(new Solution().maxProduct(nums));
    }

    static class Solution {
        /**
         * 动态规划
         * @param nums
         * @return
         */
        private int maxProduct2(int[] nums) {
            int len = nums.length;

            int[] dpMax = new int[len];// dpMax[i]表示以第 i 个元素结尾的乘积最大子数组的乘积
            int[] dpMin = new int[len];// dpMin[i]表示以第 i 个元素结尾的乘积最小子数组的乘积

            dpMax[0] = nums[0];
            dpMin[0] = nums[0];

            int res = nums[0];
            for (int i = 1; i < len; i++) {
                dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(nums[i], dpMin[i - 1] * nums[i]));
                dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(nums[i], dpMax[i - 1] * nums[i]));

                res = Math.max(res, dpMax[i]);
            }

            return res;
        }

        /**
         * 暴力法(超时)
         * @param nums
         * @return
         */
        public int maxProduct1(int[] nums) {
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j <= i; j++) {
                    res = Math.max(getProduct(nums, j, i), res);
                }
            }
            return res;
        }

        private int getProduct(int[] nums, int start, int end) {
            int product = 1;
            while (start <= end) {
                product *= nums[start++];
            }
            return product;
        }

        public int maxProduct(int[] nums) {
            return maxProduct2(nums);
        }
    }
}
